Active queue management systems are employed for controlling congestion in network devices. In any communications network, data packets received by network devices must be processed in some way. As incoming packet rates vary in a given network device, if any resource involved in the processing of data packets receives packets at a higher rate than it can process the packets, then packets will back up, effectively giving rise to a queue of data packets. Congestion occurs when resources are overloaded and the number of packets queued becomes excessive. As a simple example, network routers have a finite amount of buffer space for queuing packets awaiting transmission over outgoing links. If the incoming packet rate is too high so that resources are overloaded, queue lengths can increase to the point where router buffers are full. Network delay is also a key issue, and excessive queue lengths can give rise to unacceptable delays to network traffic.
Active queue management techniques address such problems by managing data packet queues in accordance with congestion levels with a view to avoiding adverse conditions. With token-based techniques (for example as described in Internet Engineering Task Force Request for Comments (IETF RFC) No. 2697 “A Single Rate Three Color Marker”, September 1999, and IETF RFC No. 2698 “A Two Rate Three Color Marker”, September 1999), a token counter, or “token bucket”, is associated with a queue. More particularly, a token bucket is associated with a flow of data packets to be enqueued, where a “flow” is some defined set or category of data packets, such as packets from a particular group of sources, or packets requiring a particular class of service for example. Each token represents a defined unit of data, such as a bit or byte. Tokens are continuously added to the bucket (the token count is incremented), and tokens are removed from the bucket (the token count is decremented) when packets are transmitted into the queue. More specifically, the token count is incremented at a constant rate known as the Committed Information Rate (CIR), up to a maximum upper limit on the token count known as the Committed Burst Size (CBS). At the arrival of a packet, the token count is decremented by a number of tokens corresponding to the packet size and the packet is enqueued. However, if there are insufficient tokens in the bucket, i.e. the token count is less than the packet size measured in tokens, then no decrement is made and the packet is dropped (discarded), or marked to be dropped at a later stage if necessary. In this way, queues are controlled in accordance with the availability of tokens, and excessive queue lengths can be avoided.
Active queue management systems may employ some form of feedback in the queue control mechanism based on available bandwidth in the resource to be protected. In particular, feedback based on queue occupancy is employed in some systems, since the length of a queue provides a direct measure of use of the corresponding resource and is thus a convenient indicator of bandwidth availability. For example, International Patent Application WO 02/07381 A2, published 24, Jan. 2002, discloses a domain based congestion management system in which a token bucket scheme is implemented by ingress nodes at the edge of a network domain. Bandwidth feedback is employed here in that, when a packet is enqueued, the token count is decremented by a number of tokens that varies depending on average queue length. Specifically, the number of tokens “consumed” by a packet is obtained by multiplying the packet size by a weighting factor dependent on average queue length. The weighting factor here also depends on the presence or absence of a “congestion notification” generated by core nodes in the domain based on the state of their local queues. Congestion notifications are generated by core nodes using a queue-length thresholding technique based on a modified form of the RED (Random Early Detection) system. RED is an active queue management technique wherein an average queue length is compared with a minimum and a maximum threshold. For average queue lengths above the maximum threshold all packets are dropped. For average queue lengths between the two thresholds packets are randomly transmitted into the queue with a transmit probability dependent on the average queue length. Development of the RED algorithm has given rise to further active queue management systems. For example, a scheme with a single average queue length but multiple sets of queue thresholds and maximum probabilities is known as WRED (Weighted RED). Here, the queue thresholds can be set to be fully overlapped, partially overlapped or staggered. RED with separate average queues for respective “colors” (which are used to mark packets according to some defined marking policy), and corresponding sets of minimum/maximum queue thresholds and maximum probabilities is known as RIO (RED with in/out queues). With RIO the contribution of packets to a particular color in the current total queue level can be addressed with an individual set of parameters, whereas WRED operates only on total queue size. In this respect RIO is better suited to protect lower drop precedence flows against higher drop precedence flows.
Common to all the above systems employing bandwidth feedback is that the feedback signal is based on average queue length, and this is then used directly to determine packet drop rates. While average queue length provides a useful indication of congestion status, using this directly to determine drop rates makes it difficult for network administrators to determine the correct parameter settings for operation of real networks. For example, finding the correct parameter settings where different groups of network users are offered different service levels, and for any combination of offered loads, is problematical. Moreover, in the above systems, feedback-dependent decisions on whether to transmit packets into a queue are made on a per-packet basis, requiring a significant amount of complex computation for each packet. Accordingly, it would be desirable to provide an active queue management system which alleviates some or all of the disadvantages with the above systems.